package com.cty.twentySixthDay;

/*
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 * 就是将左子树和右子树交换(每一个都交换)
 * */
public class Q_38 {
    public static void main(String[] args) {

    }
    // 主包自己写的 时间复杂度O(n)
    /*
    * 主包和官方的题解写的一样
    *  空间复杂度官方的解释
    *  平均情况是O(logN) 与树的高度有关
    *   坏的情况O(N) 所有节点都为左子节点或者右子节点时
    * */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
